package top.minuy.algorithm.sort.bubble;

/**
 * 冒泡排序算法
 * 比较简单的排序算法
 * 时间复杂度O(n²)
 * 优化1：针对后续没有进行交换操作的可以直接结束排序
 * 这个可以跳过后面有序的部分，针对完全有序数组，时间复杂度为O(n)
 * 优化2：记录最后一次交换的位置，下次从该位置开始排序
 * 这个可以跳过任意有序的部分，针对部分有序数组，时间大大减少
 *
 * @author Minuy
 * @time 9:58
 * @date 2021/9/28
 */
public class BubbleSort {
    /**
     * 不需要新建类对象
     */
    private BubbleSort() {
    }

    /**
     * 冒泡排序的默认实现，时间复杂度为O(n²)
     *
     * @param arr 待排序数组
     * @param <E> 泛型支持，可比较的
     */
    public static <E extends Comparable<E>> void sort(E[] arr) {
        //[n-i,n) 已经排好序
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }

    /**
     * 优化1
     * 在冒泡的默认实现上加了对是否发生交换操作的标记
     * 如若对后面未排序的元素遍历一遍后发现没有发生交换操作
     * 则认为后面未排序的元素为有序的元素，可以直接退出排序
     *
     * @param arr 待排序数组
     * @param <E> 泛型支持，可比较的
     */
    public static <E extends Comparable<E>> void sort1(E[] arr) {
        //[n-i,n) 已经排好序
        boolean isSwapped;
        for (int i = 0; i < arr.length; i++) {

            isSwapped = false;
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                    isSwapped = true;
                }
            }

            if (!isSwapped) {
                break;
            }
        }
    }

    /**
     * 优化2
     * 在冒泡的默认实现上加了对最后交换位置的标记
     * 对于后面小部分有序的部分也可以直接跳过
     *
     * @param arr 待排序数组
     * @param <E> 泛型支持，可比较的
     */
    public static <E extends Comparable<E>> void sort2(E[] arr) {
        //[n-i,n) 已经排好序
        int lastSwappedIndex;
        for (int i = 0; i < arr.length; ) {

            lastSwappedIndex = 0; // 最后一次交换的位置
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    swap(arr, j, j + 1);
                    lastSwappedIndex = j + 1; // 记录最后一次交换的位置
                }
            }

            i = arr.length - lastSwappedIndex; // 调整已经排序好的内容
        }

    }

    /**
     * 交换数组中的两个元素
     *
     * @param arr 数组
     * @param i   元素1下标
     * @param j   元素2下标
     * @param <E> 泛型支持
     */
    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[j];
        arr[j] = arr[i];
        arr[i] = t;
    }

}
